package leetcode_2301_2400;

public class LeeCode_2400 {
    public static void main(String[] args) {
        System.out.println(numberOfWays(1, 2, 3));
        System.out.println(numberOfWays(2, 5, 10));
        System.out.println(numberOfWays(1, 1, 4));
    }

    private static int numberOfWays(int startPos, int endPos, int k) {
        if (Math.abs(startPos - endPos) > k) {
            return 0;
        }
        long mod = (long) (1e9 + 7);
        long[][] dp = new long[k * 2 + 1][k + 1];
        dp[k + startPos - endPos][0] = 1;
        for (int i = 1; i <= k; i++) {
            dp[0][i] = dp[1][i - 1] % mod;
            for (int j = 1; j < dp.length - 1; j++) {
                dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
                dp[j][i] %= mod;
            }
            dp[dp.length - 1][i] = dp[dp.length - 2][i - 1] % mod;
        }
        return (int) dp[k][k];
    }
}
